iT邦幫忙

2023 iThome 鐵人賽

DAY 23
0

https://ithelp.ithome.com.tw/upload/images/20231009/20149362qIIkTNlkAB.png
圖片來源
今天要來討論堆疊(Stack)和佇列(Queue)的概念,就以前端面試來說這個題目是常見的,網路上應該都可以找到很多相關資訊。當你了解stack 和 queue 是什麼,對 JS 的非同步也會更有概念

▌堆疊(Stack)是什麼?

https://ithelp.ithome.com.tw/upload/images/20231008/20149362hJJOAb5E5S.jpg
堆疊是一種具有順序性的資料結構,有以下兩種特性(存取方式):

  • 後進先出(Last In First Out, LIFO):最後放的資料會最先被取出
  • 先進後出(First In Last Out, FILO):最先放的資料會最後被取出

把堆疊儲存資料的方式看成上面這張插收據、紙張的插單器,只會進行兩個動作,「Push」在最上面插入新的紙、「Pop」撕掉最上面的紙。只允許資料在單一位置端增加或減少,並且沒有 index ,所以沒有辦法直接訪問
https://ithelp.ithome.com.tw/upload/images/20231008/20149362pxZ1CzeSCv.png
取自維基百科

javaScript 就有內建實作堆疊的方法,push 會將一個或多個元素添加到陣列的末尾,而 pop 用於刪除陣列的最後一個元素

let stack = [];
// 存入堆疊(push)
stack.push("a");
stack.push("b");
stack.push("c");

// 從堆疊取出(pop)
let c = stack.pop();
let b = stack.pop();
let a = stack.pop();

▪ 堆疊的應用

我們可以利用一維陣列(Array)和鏈接串列(Linked List)來實作「堆疊」。以下是幾個應用情境

  • 函式呼叫(Function Call)時
    又可叫「呼叫堆疊」(Call Stack),注意!這裡的呼叫是指呼叫函式時所使用的堆疊,而不是去呼叫一個堆疊喔!系統需要追蹤每個 function 的執行狀態,包括該 function 的本地變數、執行位置和返回點(即 function 完成後應該返回的位置)。這種函數執行狀態的追蹤通常是使用堆疊(Stack)來實現的

  • 遞迴(Recursive)
    堆疊保存了當前遞迴調用的狀態,以便在結束時能夠恢復原本狀態

  • 瀏覽某個網頁時,可以按下「上一頁」一直返回

  • 記錄操作的歷史記錄
    平常我們在用 command + Z(Ctrl + Z)恢復先前操作時,就是堆疊的概念,每按一次command + Z,就會從抹除最後一個操作記錄!堆疊是一個非常靈活的資料結構,可以用於許多不同的情境中,以解決各種問題

以下附上幾個 Leecode 與 stack 有關的題目:

  1. 有效的括號(Valid Parentheses)
    這題要用堆疊來檢查括號是否是一致成對的

  2. 簡化路徑(Simplify Path)
    這題需要使用堆疊來處理路徑中的 "." 和 ".."

▌佇列(Queue)

https://ithelp.ithome.com.tw/upload/images/20231008/20149362uFvMPAexVs.png
圖片來源

佇列又稱「隊列」,跟堆疊一樣是一個有順序性的資料結構,不過新增與刪除發生在串列的兩端。新增的端點稱為「尾端」(Rear, Tail, Back),只能在佇列的末端才能進行,在佇列裡新增元素,在計算機領域中又稱為 「Enqueue」。「刪除」的端點稱為前端(Front),只能在佇列的開頭才能進行!而移除佇列中的元素又稱為「Dequeue」。具有先進先出(First In First Out,FIFO)的特性,跟 stack 一樣都沒有 index

▪ 佇列的應用

實作上,經常以陣列或鏈結串列(Linked list)來實現。可以把佇列的概念想像成是排隊!當多個人排隊等待服務時,第一個到達的就會先被服務到,越後面來的,就越慢服務到。在軟體開發中,隊列用於管理待處理的任務,確保它們按照特定順序進行處理

  • 在多執行序的語言中,會共享的任務佇列,以確保線程按照 FIFO 順序執行任務
  • 在單線程應用中,可以管理工作流程、事件處理和非同步操作,提高應用程序的效率、可讀性和可維護性

附上 Leecode 上與 Queue 有關的題目:

1.Implement Stack using Queues

2.Implement Queue using Stacks

▌總結

堆疊和佇列都是應用廣泛的典型資料結構之一。堆疊常見的應用情境像是函式呼叫時,打開 F12 的 source 就會看到右邊有 call Stack 的視窗,只要在程式碼中下中斷點(debugger)就能看到函式的呼叫順序,藉此尋找問題;佇列常見的應用情境大多具有一個特徵:暫時存放,稍候執行,並且一定會按先來後到的順序執行。兩者最大的差別就是堆疊執行的端點為同一端,佇列則有兩端

在談論了 Stack 和 Queue 之後,要理解前端很常考的面試題目 - Event Loop 就會比較容易一點! javaScript 是個 Single Thread 的程式語言,一次只能做一件事情,所以 Stack 會把裡面的任務「由上而下」依序處理,每處理完一個片段就移除,直到Stack 為空,這時 queue 如果還有排隊等候的任務就會加入到 stack 裡面,這個過程稱為 Event Loop

https://ithelp.ithome.com.tw/upload/images/20231008/20149362Yuxpw1Jw3G.png

event loop demo 線上演示器,可以看到 function 的執行狀態

▌參考資料

  1. 堆疊(stack)是什麼
  2. 佇列(Queue)是什麼?
  3. leecode - stack
  4. leecode - queue

上一篇
Day 22 | 樹狀結構 (Tree) - 你要了解的節點觀念
下一篇
Day 24 | 演算法:Big O Notation & 最大最小數找法
系列文
來場計概入門課吧X資訊人該了解的通識素養31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言